/*
 * Copyright (c) 2009-2010 HIT Microelectronic Center
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 *
 * Authors: Gou Pengfei
 *
 * Date: Dec. 2009
 *
 */
#include <algorithm>
#include <cstring>

#include "base/types.hh"
#include "config/the_isa.hh"
#include "arch/isa_traits.hh"
#include "cpu/edge/block.hh"
#include "base/bitfield.hh"
#include "base/trace.hh"
#include "base/loader/symtab.hh"

template<class Impl>
SimpleEdgeBlock<Impl>::SimpleEdgeBlock(BlockID blockID, CPU* cpu)
    : BaseEdgeBlock<Impl>(blockID, cpu)
{
    mark = 0;
    type = 0;
    xFlags = 0;
    sMask = 0;
    chunkNum = 0;

    branchTarget = 0;
    predBranchTarget = 0;
 
    // Init frame id to be invalid.
    frameID = -1;

    sMaskFlag.reset();
    readMask.reset();
    writeMask.reset();
    exitMask.reset();

    // Predication status is initilized to be False.
    predicationStatus.reset();

    testInstPath.reserve(TheISA::MaxInstsInBlock);
    testInstPath.clear();

    exitID = 0xffffffff;
    predExitID = 0xffffffff;

    exitType = TheISA::InvalidExitType;
    predExitType = TheISA::InvalidExitType;

    numReceivedStore = 0;
    numReceivedWrite = 0;
    numReceivedExit = 0;

    executedInsts = 0;    
    executedMovs = 0;

    instContainer.resize(TheISA::MaxInstsInBlock, NULL);
    ldstContainer.resize(TheISA::MaxLdstsInBlock);
    readContainer.resize(TheISA::HeaderSize, NULL);
    writeContainer.resize(TheISA::HeaderSize, NULL);
}

template<class Impl>
SimpleEdgeBlock<Impl>::~SimpleEdgeBlock(){}

template<class Impl>
void
SimpleEdgeBlock<Impl>::addInst(DynInstPtr &inst, int position)
{
    // Instruction that has the same ID of this block is allowed to be
    // added.
    assert(this->blockID == inst->getBlockID());
    // We can never add mulptiple instructions to the same position.
    assert(!instContainer[position]);
    // Register read/write can not be added using this method.
    assert(!inst->isRead() && !inst->isWrite());

    // This is rather obvious.
    assert(position < TheISA::MaxInstsInBlock);

    // Every inst should be added into instContainer including ld/st.
    instContainer[position] = inst;

    if (inst->isMemRef()) {

        TheISA::LsID inst_lsid = inst->staticInst->getLSID();
        
        ldstContainer[inst_lsid].instContainerIdxs.push_back(position);
        
        if (inst->isStore()) {
            // The same ldstEntry can only be accessed by the same
            // type of memory reference. That means the same entry
            // should always be load entry or always be store entry.
            assert(!(ldstContainer[inst_lsid].valid) || 
                    (ldstContainer[inst_lsid].valid && ldstContainer[inst_lsid].store));

            ldstContainer[inst_lsid].store = true;
        } else if (inst->isLoad()) {
            assert((!ldstContainer[inst_lsid].valid) || 
                    (ldstContainer[inst_lsid].valid && !ldstContainer[inst_lsid].store));

            ldstContainer[inst_lsid].store = false;
        }

        ldstContainer[inst_lsid].valid = true;

        DPRINTF(EdgeBlock, "Adding load/store insts[lsid:%i].\n",
            inst->staticInst->getLSID());
    }

    if (inst->isControl()) {
        TheISA::ExitID exit_id = inst->staticInst->getEXIT();
        assert(exit_id < TheISA::MaxExitsInBlock);
        exitMask.set(exit_id);

        /** Sequential target type is not known util the block is
         * executed, so we're not able to set flags for a sequential type
         * exit at this stage. */
        if (inst->isCall()) {
            this->typeFlags.set(TheISA::call);

            if (inst->isIndirectCtrl()) {
                this->completeTypeFlags.set(2);
            } else {
                this->completeTypeFlags.set(3);
            }
        } else if (inst->isReturn()) {
            this->typeFlags.set(TheISA::ret);

            this->completeTypeFlags.set(4);
        } else {
            this->typeFlags.set(TheISA::branch);

            if (inst->isIndirectCtrl()) {
                this->completeTypeFlags.set(0);
            } else {
                this->completeTypeFlags.set(1);
            }
        }
    }

    DPRINTF(EdgeBlock,"tid[%i] -- PC:%#x\n",
            inst->threadNumber,
            inst->readPC());

    DPRINTF(EdgeBlock, "Blcok ID: %lli -- Chunk ID: %lli -- Inst ID: %lli\n",
            inst->getBlockID(), 
            inst->getChunkID(), 
            inst->getInstID());

    DPRINTF(EdgeBlock, "Instruction is: %s\n\n",
            inst->staticInst->disassemble(inst->readPC()));
}

template<class Impl>
typename SimpleEdgeBlock<Impl>::DynInstPtr
SimpleEdgeBlock<Impl>::getInst(int position)
{
    assert(position < chunkNum * TheISA::ChunkSizeInWords);

    DynInstPtr inst = instContainer[position];

    return inst;
}

template<class Impl>
void
SimpleEdgeBlock<Impl>::addHead(DynInstPtr &inst, int position)
{
    assert(inst->isRead() || inst->isWrite());
    assert(position < TheISA::HeaderSize);

    if (inst->isRead()) {
        assert(!readContainer[position]);

        readContainer[position] = inst;

        readMask.set(position);

    } else if (inst->isWrite()) {
        assert(!writeContainer[position]);

        writeContainer[position] = inst;

        writeMask.set(position);

    } else {
        panic("Unrecogonized head insts.\n");
    }

    DPRINTF(EdgeBlock,"tid[%i] -- PC:%#x\n",
            inst->threadNumber,
            inst->readPC());

    DPRINTF(EdgeBlock, "Blcok ID: %lli -- Chunk ID: %lli -- Inst ID: %lli\n",
            inst->getBlockID(), 
            inst->getChunkID(), 
            inst->getInstID());

    DPRINTF(EdgeBlock, "Instruction is: %s\n\n",
            inst->staticInst->disassemble(inst->readPC()));

}

template<class Impl>
typename SimpleEdgeBlock<Impl>::DynInstPtr
SimpleEdgeBlock<Impl>::getRead(int position)
{
    assert(readContainer[position]);

    DynInstPtr read = readContainer[position];

    return read;
}

template<class Impl>
typename SimpleEdgeBlock<Impl>::DynInstPtr
SimpleEdgeBlock<Impl>::getWrite(int position)
{
    assert(writeContainer[position]);

    DynInstPtr write = writeContainer[position];

    return write;
}

template<class Impl>
std::vector<int>&
SimpleEdgeBlock<Impl>::getMemoryReferenceIdx(TheISA::LsID lsid)
{
    assert(ldstContainer[lsid].valid);
    assert(ldstContainer[lsid].instContainerIdxs.size() > 0);

    return ldstContainer[lsid].instContainerIdxs;
}

template<class Impl>
void
SimpleEdgeBlock<Impl>::removeAllInsts()
{
    instContainer.clear();
    ldstContainer.clear();
    readContainer.clear();
    writeContainer.clear();

    writeMask.reset();
    readMask.reset();
    
    this->numWrites = 0;
    this->numReads = 0;
    this->numMemRefs = 0;
    chunkNum = 0;
    sMask = 0;
}

template<class Impl>
bool
SimpleEdgeBlock<Impl>::depackHeader(HeaderInfo& info)
{
    assert(info.size() >= TheISA::HeaderInfoSize);

    mark = bits(info[3], 31, 24 );
    type = bits(info[3], 23, 16);
    xFlags = bits( info[3], 15, 8 );
    sMask = info[1];
    chunkNum = ( type == 0 ) ? 4 : type;

    if(chunkNum > 4) {
        chunkNum = 1;
    }

    // As we know how many chunks this block has, we can set the next
    // block PC in program order
    nextBlockPC = this->startAddr + (chunkNum + 1) * TheISA::ChunkSize;

    // Currently do nothing but dprint it
    DPRINTF(EdgeBlock, "\nBlockID %d -- Block StartAddress 0x%#x -- "
            "NextBlockAddress 0x%#x\n",
            this->blockID, 
            this->startAddr, 
            nextBlockPC );

    DPRINTF (EdgeBlock, "Header MARK : 0x%x\n"
            "Header TYPE : 0x%x\nHeader XFLAGS : 0x%x\n"
            "Header SMASK : 0x%x\n", 
            mark, type, xFlags, sMask);

    if (mark != 0xff) {
        //warn ("Wrong header at blockID %d -- Block StartAddress 0x%#x!\n",
               //      this->blockID, this->startAddr);
        return false;
    } 

    return true;
}

template <class Impl>
void
SimpleEdgeBlock<Impl>::map()
{
    // Mapping reg idx of reg-write. 
    // Mapping strategy comes from trips doc.
    for (int i = 0; i < TheISA::HeaderSize; i++) {
        if (writeMask[i]) {

            DynInstPtr inst = writeContainer[i];

            assert(inst);

            int num_regs = inst->numDestRegs();

            for (int idx = 0; idx < num_regs; idx++) {

                PhysRegIndex mapped_idx =
                    inst->getInstID() % 4 + inst->destRegIdx(idx) * 4;

                inst->mapDestReg(idx, mapped_idx);

                DPRINTF(EdgeBlock, "Mapping dest reg from %idx to %idx\n",
                    inst->destRegIdx(idx), mapped_idx);
            }
        }
    }

    // Mapping reg reads and its consumers.
    // Mapping strategy comes from trips doc.
    for (int i = 0; i < TheISA::HeaderSize; i++) {
        if (readMask[i]) {

            DynInstPtr inst = readContainer[i];

            assert(inst);

            int num_regs = inst->numSrcRegs();

            for (int idx = 0; idx < num_regs; idx ++) {

                PhysRegIndex mapped_idx =
                    inst->getInstID() % 4 + inst->srcRegIdx(idx) * 4;

                inst->mapSrcReg(idx, mapped_idx);

                DPRINTF(EdgeBlock, "Mapping src reg from %i to %i\n",
                    inst->srcRegIdx(idx), mapped_idx);
            }

            int num_consumers = inst->getNumConsumers();

            for (int idx = 0; idx < num_consumers; idx++) {

                ConsumerBitfield consumer_raw_bit = 
                    inst->getRawConsumerID(idx);

                inst->setConsumerType(idx, consumer_raw_bit.type);

                if (consumer_raw_bit.type == TheISA::WriteSlotOrNoTarget) {

                    if (consumer_raw_bit.subtype == TheISA::WriteSlot) {

                        inst->setConsumerSubType(idx, TheISA::WriteSlot);
                        inst->setConsumerID (idx, consumer_raw_bit.write_id);
                        
                    } else if (consumer_raw_bit.subtype == TheISA::NoTarget) {

                        inst->setConsumerSubType(idx, TheISA::NoTarget);
                        inst->setConsumerID (idx, 0);

                    } else {
                        panic("Unrecogonized consumer subtype\n");
                    }

                } else {
                    inst->setConsumerID (idx, consumer_raw_bit.id);
                }

                DPRINTF(EdgeBlock, "Consumer[idx:%i][Type:%i][ID:%i]\n", 
                        idx,
                        consumer_raw_bit.type,
                        consumer_raw_bit.id);
            }

        }
    }
    
    // Mapping the body instructions.
    // Mapping strategy comes from trips doc.

    for (int i = 0; i < TheISA::ChunkSizeInWords * chunkNum; i++) {

        DynInstPtr inst = instContainer[i];

        // Nops are NULL pointer, so avoid mapping them.
        if (inst) {

            int num_consumers = inst->getNumConsumers();

            for (int idx = 0; idx < num_consumers; idx++) {

                ConsumerBitfield consumer_raw_bit = 
                    inst->getRawConsumerID(idx);

                inst->setConsumerType(idx, consumer_raw_bit.type);

                if (consumer_raw_bit.type == TheISA::WriteSlotOrNoTarget) {

                    if (consumer_raw_bit.subtype == TheISA::WriteSlot) {

                        inst->setConsumerSubType(idx, TheISA::WriteSlot);
                        inst->setConsumerID (idx, consumer_raw_bit.write_id);
                        
                    } else if (consumer_raw_bit.subtype == TheISA::NoTarget) {

                        inst->setConsumerSubType(idx, TheISA::NoTarget);
                        inst->setConsumerID (idx, 0);

                    } else {
                        panic("Unrecogonized consumer subtype\n");
                    }

                } else {
                    inst->setConsumerID (idx, consumer_raw_bit.id);
                }

                DPRINTF(EdgeBlock, "Consumer[idx:%i][Type:%i][ID:%i]\n", 
                        idx,
                        consumer_raw_bit.type,
                        consumer_raw_bit.id);
            }
        }
    }

    return;
}

template<class Impl>
bool
SimpleEdgeBlock<Impl>::isCompletionCondSatisfied()
{
    DPRINTF(EdgeBlock, "Block[id:%lli] has received "
            "%i writes, %i stores and %i exits.\n",
            this->getBlockID(),
            numReceivedWrite,
            numReceivedStore,
            numReceivedExit );

    return (this->getNumRegWriteInst() == numReceivedWrite) &&
           (sMask == sMaskFlag.to_ulong()) &&
           (numReceivedExit == 1);
}

template<class Impl>
void
SimpleEdgeBlock<Impl>::setBranchTarget(Addr branch_pc)
{
    // Make sure this is an chunk-aligned address
    // Sometimes a mispredicted series of blocks will
    // set the branch target to silly value. This 
    // will not affect the output due to 
    // misprediction handling methods.
    //assert( (branch_pc & TheISA::ChunkOffset) == 0);

    branchTarget = branch_pc;
}

template<class Impl>
void
SimpleEdgeBlock<Impl>::setPredBranchTarget( Addr pred_branch_pc )
{
    assert((pred_branch_pc & TheISA::ChunkOffset) == 0);

    predBranchTarget = pred_branch_pc;
}

template<class Impl>
void
SimpleEdgeBlock<Impl>::setNextBlockPC( Addr next_block_pc )
{
    // Make sure this is an chunk-aligned address
    assert((next_block_pc & TheISA::ChunkOffset) == 0);
    nextBlockPC = next_block_pc;
}

template<class Impl>
bool
SimpleEdgeBlock<Impl>::misPredicted()
{
    if (exitType == TheISA::seq) 
      DPRINTF(EdgePredUnit,"Exit type is seq.\n");     
    else if (exitType == TheISA::branch)
      DPRINTF(EdgePredUnit,"Exit type is branch.\n");
    else if (exitType == TheISA::call)
      DPRINTF(EdgePredUnit,"Exit type is call.\n");
    else if (exitType == TheISA::ret)
      DPRINTF(EdgePredUnit,"Exit type is return.\n");
    else
      panic("Unknown branch type!");
      
    assert(exitType == TheISA::branch || 
           exitType == TheISA::call ||
           exitType == TheISA::ret ||
           exitType == TheISA::seq);
                         
    if (exitID != predExitID) {
        DPRINTF(EdgePredUnit,"[Bid:%i][PC:%#x]: eixt is mispredicted! "
                "Actual exit is %i while predicted exit is %i. Target is"
                " %#x.\n",
                this->blockID,
                this->getStartPC(),
                this->exitID,
                this->predExitID,
                this->branchTarget);
        
    } else if (branchTarget != predBranchTarget) {
        DPRINTF(EdgePredUnit,"[Bid:%i][PC:%#x]: target is mispredicted!"
                "Actual target is %#x while predicted target is %#x.\n",
                this->blockID,
                this->getStartPC(),
                this->branchTarget,
                this->predBranchTarget);
        
    }

    if (branchTarget != predBranchTarget) {
        return true; 
    } 

    DPRINTF(EdgePredUnit,"[Bid:%i][PC:%#x]:predict correctly!\n",
            this->blockID,
            this->getStartPC());

    return false;
}

template<class Impl>
bool
SimpleEdgeBlock<Impl>::exitMispredicted()
{
    if (exitID != predExitID) {
        return true;
    }

    return false;
}

template<class Impl>
bool
SimpleEdgeBlock<Impl>::exitTypeMispredicted()
{
    if (exitType != predExitType) {
        return true;
    }
    return false;
}

template<class Impl>
bool
SimpleEdgeBlock<Impl>::seqMispredicted()
{
    if (exitType != predExitType) {
        if (exitType == TheISA::seq || predExitType == TheISA::seq) {
            return true;
        }
    }
    return false;
}

template<class Impl>
TheISA::LsID
SimpleEdgeBlock<Impl>::getLastStore(TheISA::LsID lsid)
{
    assert(lsid < TheISA::StoreMaskNum);

    DPRINTF(EdgeBlock, "Get last store for LSID %i\n", lsid);

    if (lsid == 0) return -1;

    while (!bits(sMask, --lsid)) {
        if (lsid == 0) return -1;
    }

    DPRINTF(EdgeBlock, "Last store is LSID %i\n", lsid);

    return lsid;
}

template<class Impl>
TheISA::LsID
SimpleEdgeBlock<Impl>::getMemBlockerLSID()
{
    assert(sMask > 0);

    uint32_t status = sMask ^ ((uint32_t)sMaskFlag.to_ulong());

    TheISA::LsID blocker_lsid = findLsbSet(status);

    return blocker_lsid;
}

template<class Impl>
void
SimpleEdgeBlock<Impl>::recordExitType(bool isCall, bool isReturn, bool isIndirect)
{
    assert(!(isCall & isReturn));

    if (isCall) {
        exitType = TheISA::call;
    } else if (isReturn) {
        exitType = TheISA::ret;
    } else if (this->branchTarget == this->nextBlockPC) {
        exitType = TheISA::seq;
    } else {
        exitType = TheISA::branch;
    }
}

template<class Impl>
void
SimpleEdgeBlock<Impl>::dumpOutput()
{
#ifndef NDEBUG
    if (DTRACE(EdgeBlockOutput)) {

        std::string sym_str;
        Addr sym_addr;
        debugSymbolTable->findNearestSymbol(this->getStartPC(),
                                            sym_str, sym_addr);

        DPRINTFNR("PC %#x\n.BLOCK %s\n",
                  this->getStartPC(), sym_str.c_str());

        std::vector<DynInstPtr> temp_stores;
        std::vector<DynInstPtr> temp_writes;

        uint32_t store_mask = sMask;
        for (int idx = 0; (idx < ldstContainer.size()) && (store_mask > 0); idx++) {
            if (store_mask & 0x1) {
                assert(ldstContainer[idx].valid && 
                    ldstContainer[idx].executed && 
                    ldstContainer[idx].store);    
                    
                int store_id = ldstContainer[idx].executedInstIdx;
                assert(store_id >= 0 && 
                       store_id < chunkNum * TheISA::ChunkSizeInWords);

                if (ldstContainer[idx].nullified) {
                    DPRINTF(EdgeBlock, "Nullified"
                            " store[LSID:%i].\n", 
                            idx);
                    store_mask >>= 1;
                    continue;
                }

                DynInstPtr store_inst = instContainer[store_id];

                assert(store_inst->isStore() && 
                       !store_inst->isNullified());

                temp_stores.push_back(store_inst);
                
            }
            store_mask >>= 1;
        }

        std::sort(temp_stores.begin(), temp_stores.end(), effAddrComp());

        for (int idx = 0; idx < temp_stores.size(); idx++) {

            DPRINTFNR("M[%#x,%i] %#x\n", 
                      temp_stores[idx]->effAddr,
                      temp_stores[idx]->memAccSize,
                      temp_stores[idx]->getIntIQOperand(1));
        }
        
        temp_stores.clear();

        for (int idx = 0; idx < writeContainer.size(); idx++) {

            if (!writeMask[idx]) {
                continue;
            }

            DynInstPtr write_inst = writeContainer[idx];

            assert(write_inst);

            if (write_inst->isNullified()) {
                DPRINTF(EdgeBlock, "Nullified write[Wid:%i].\n", 
                        idx);
                continue;
            }

            temp_writes.push_back(write_inst);
        }

        std::sort(temp_writes.begin(), temp_writes.end(), registerIdxComp());

        for (int idx = 0; idx < temp_writes.size(); idx++) {

            DPRINTFNR("G[%i] %#x\n", 
                      temp_writes[idx]->getMappedDestReg(0),
                      temp_writes[idx]->getIntIQOperand(0));            

        }

        temp_writes.clear();
    }

#endif
}

template<class Impl>
void
SimpleEdgeBlock<Impl>::setSyscallBranchTarget()
{
    assert(this->isNeedSyscall());
    assert(this->isCompleted());

    for (int idx = 0; idx < TheISA::HeaderSize; idx++) {
        if (writeMask[idx]) {

            DynInstPtr write_inst = writeContainer[idx];

            assert(write_inst->isExecuted());

            if (write_inst->getMappedDestReg(0) == TheISA::ReturnAddressReg &&
                !write_inst->isNullified()) {

                Addr ret_addr = write_inst->getIntIQOperand(0);

                setBranchTarget(ret_addr);
                recordExitType(false,true,false);

                // We are expecting only one write is matched.
                return;
            }
        }
    }

    DPRINTF(EdgeBlock, "Can't find branch target for this syscall block.\n");

    warn("Can't find branch target for a syscall block."
         " Maybe an exit syscall is isssued.\n");
}

